//给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 
//
// 你需要返回给定数组中的重要翻转对的数量。 
//
// 示例 1: 
//
// 
//输入: [1,3,2,3,1]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: [2,4,3,5,1]
//输出: 3
// 
//
// 注意: 
//
// 
// 给定数组的长度不会超过50000。 
// 输入数组中的所有数字都在32位整数的表示范围内。 
// 
// Related Topics树状数组 | 线段树 | 数组 | 二分查找 | 分治 | 有序集合 | 归并排序 
//
// 👍 364, 👎 0 
//
//
//
//

package leetcode.editor.cn;

class ReversePairs {
    public static void main(String[] args) {
        Solution solution = new ReversePairs().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        int count = 0;  // 翻转个数
        int[] temp;

        public int reversePairs(int[] nums) {
            int n = nums.length;
            temp = new int[n];
            sort(nums, 0, n - 1);
            return count;
        }

        public void sort(int[] nums, int l, int r) {
            if (l == r) {
                return;
            }

            int m = l + (r - l) / 2;

            sort(nums, l, m);
            sort(nums, m + 1, r);
            merge(nums, l, m, r);
        }

        public void merge(int[] nums, int l, int m, int r) {
            for (int i = l; i <= r; i++) {
                temp[i] = nums[i];
            }

            // 找到翻转对
            // 由于前面[l, mid]已经排好序的，所以计算后面的可以直接使用前面的end位置在进行判断
            // 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
            // 为什么 end 是开区间？因为这样的话可以保证初始区间 [mid+1, mid+1) 是一个空区间
            int end = m + 1;
            for (int i = l; i <= m; i++) {
                while (end <= r && (long) nums[i] > (long) 2 * nums[end]) {
                    end++;
                }
                count += end - (m + 1);
            }

            int i = l, j = m + 1;
            for (int k = l; k <= r; k++) {
                if (i == m + 1) {
                    nums[k] = temp[j++];
                } else if (j == r + 1 || temp[i] < temp[j]) {
                    nums[k] = temp[i++];
                } else {
                    nums[k] = temp[j++];
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
